package com.cqs.leetcode;

/**
 * Created by cqs on 2018/3/25.
 */
public class MinimumRotatedSortedArray {

    public int findMin2(Integer[] nums) {
        int left = 0, right = nums.length - 1, mid = 0;
        int min = nums[0];
        while (left <= right) {
            mid = (left + right) / 2;
            min = Math.min(min, nums[mid]);
            if (nums[mid] < nums[left]) {//右侧单调非减
                //nums[mid] 就是min的值
                if (nums[mid] < nums[mid - 1]) return min;
                //nums[mid] 不是min的值
                right = mid - 1;
            } else if (nums[mid] == nums[left]) {//没有重复的元素 那只能说明 left = mid 也就是 也就是right==left 或者 right==left+1
                return Math.min(min, Math.min(nums[left], nums[right]));
            } else {
                //单调非减
                if (nums[left] <= nums[right]) return nums[left];
                left = mid + 1;
            }
        }
        return min;
    }

    public int findMin(Integer[] nums) {
        int left = 0, right = nums.length -1, mid = 0, min = nums[0];
        while (left <= right) {
            mid = (left + right) / 2;
            min = Math.min(min, nums[mid]);
            if (nums[mid] < nums[left]) {
                //nums[mid]就是min
                if (nums[mid] < nums[mid - 1]) return min;
                right = mid - 1;
            } else if (nums[mid] == nums[left]) {
                return Math.min(min, Math.min(nums[left], nums[right]));
            } else {
                //单调非减
                if (nums[left] <= nums[right]) return Math.min(min, nums[left]);
                left = mid + 1;
            }
        }
        return min;
    }
}
